import libnum
import gmpy2
import random
import uuid

n1 = 15229908966215673498264833619915862067189414881076960436877368615098175680441463135574405877266084016930270486805823866233100564302504890309012014811833355036803313503898478169492755564750400014950957968738560644049839456859498610733352635085343594112468877475531058156406714101260523668718601047825031099622949295499360227422532501547624931966301078524006797464247562465148669456759919516529290118434601009165995947159321449572614699448476100967664566619009059134422233825969331748148860489619925702309297146477957965828540943526221853964005609999026637516521464246318660977046648835810455829429341968774818398723853
n2 = 16647671303452992814874916736670768507126337287566806803856358971599504932626835696964451452343832014324551312290172667506710009528951994807498255871494566471000537304568754858163291490985871966879235032991671329249773447655311105094011323544857528388925766738036851981411914648354588379859727189184060795755469840504119808662263041034859662007459121199866617211978706354395021326856422186021481792874584360726451742152401574782594951342548837410441200290733338032526353513084793937984997949578170760791903999736291842181621963250574851421507831701064063912449849413172670241330884387514421259190912380383298164284999
n3 = 29741021686246020663676841105136775419357440781390260185592393569401376370805978457667540637964200363607306500686262920691759678594031678300413142185183670884962159744553489320946009596478586998527067077134149278862373300775784094204755592034106781470475619885674201222026771053219023490292688620343351009379638231445481201297167271847129926702267108223608485623131033339305214837391614096507988954783053070796974148251216158278106592716506313630837162027599129553042520944246264174701211107075008419327392352704491698073652799599537256566759453566984344533606287599484285948531866987190797600263099518976935518240853

c1 = 6959258084092071065454299562288093923928417805928999659456406888937711509968856448163724527178151995480998144115831503011062045998734828883932412902319165009103141785130495087527312884494217049521337026706981996133432121798284172867545561634801496799668796585567711427864913170983434124205704168783854067763295351235413293017461040137295238173652253470527795039349714605669787423743618096196647453389748359636276835096715488576301332996050701277261859215493749088704184934893541297337697890057228935005941328617003209076420546007716706353983380827300196405400201116416777230463275285732458512616567135941354467426685
c2 = 6980329295285525362547267847848318865994479894934736155773709405141249106739972526023147681931864449293251687818166317241310314795104094837920560848283265330877221117715222738878585798211133044997504018312371879793223144496711763354586556889478112149480922447037459440851037495694217691645394427027614927170296896917587773256575272276914565557013085090885698797535297051218113044222599072597256695709554731560694742808401895251490618749646636594613484000904930914249322765325562362771885023000308531495515513151456771016399566960453308004677247446640121091968613983880226467225115682271606727631686032091291561140665
c3 = 20233993944978872042376344612943348102384153122558951915884274540138133554880115520330270710436883503022447682261018630693003219118284031617386534453929979962484430097693138337783002193192655501743050154775785535891890220923675994415232467097451208945510241779558595207425558347996942813211797652323984401196168255438306008115570489036147326159800446645923532611587932910081212717758849963264411492688567511495848103724155361462459108323999586803944933759202774033308915621722956400626498734688034239662478280986247839989724798426875779835896165243527034531628504097837684091017613599431520636356624353558008613223963


def GCRT(m, a):
    assert (len(m) == len(a))
    curm, cura = m[0], a[0]
    for m, a in zip(m[1:], a[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
    return cura % curm


n = [n1, n2, n3]
c = [c1, c2, c3]
mm = libnum.solve_crt(c, n)
print(mm)
for e in range(10, 20):
    m, t = gmpy2.iroot(mm, e)
    if t:
        print(m)
        print(libnum.n2s(int(m)))

import libnum

e = 13
n1 = 16655230929893303490818415854457831426545038662809855283873228642358207995734291242944120042612699642460820594813654718158395826755230956722936107927889550129166619245152453353908373751380196656611349200623414836128383308653618062999595622747482867683840133843768870236300348203389275090871132570173650238774275209757683812077533989960172822335488251744796657926473009279723460304257252876756936524918018903158795894385111046938638194925881670388700872760201130485273663156422785999102754192840209476417602399017445296045070405343876349687582470436774316410697773759057621576657298096301937899052773787116133124199739
n2 = 17197151926745749646602149115445210421300330711044282276861045275221683290586877554048509794473112203880585601275129330843554946888863132721219683639579200702355880529569042889789589005950061966309684759066705732225014741164779016525568884409690021988879475589545329149547046975086877521757237117008484775731784935960191717287332176327498377273179740487245459081737196777751408106728622513560888261855065717079007065635401835089216224111969668029246916986663313301660909538148574652809266532053889578734157117390082522831069594417637550812101652367765364077901612478983024721669687150628356918237152414368862535409859
n3 = 18719461901666732419189610536735130974364055134601694187780706398369536769336080321122034942831217438281120989017698755904233940669427542442488330152862658754609065361849067002424120904308655036927580582916373684567047102601602588472175947665724244201887952599804681827419266055359412641159981152796138695901074514583606207162167385730873921563442166111892785482387108299191119048884993267729877797586421940344366636285656854837470348603688925980178978612114344024951042846249621559376348599687263736342957456838732355009637030035658212442442824658869094581324944034490700706979663405137522294780606800571433058912041


c1 = 3530761236149189046680124371485374220252032991305088864647979778627799354583229731576585900490173357726425570018182390597284149666834264690795437972634538596441103368165128688664787322126097802985602065455316693754513332761284857157982201975554297034291092099307950246864758375115838291339394148547902128382917596947095456178572561422004708150053706114994560773293625641699691472764190426577272488084620105693964419578988589192873196530900413833531923536786853211065167782657153004342018675666293830194703777994380600060782651326623229047839109994778831432598543154184891096335217588164509636922274833553782288823349
c2 = 7557835478962501903223351987016911891266554255050134264644805724502475848487138948948076311894495847429608136390014902405718084026208891531815323418707377349405409096779206918831458396991602033494429461919844309109113047361743133772636443322195238900874786548606687215969337920658068807801603115402783849082788527952834594443136756890747461628705174983562847145588532659589787532039981477468881131005056101092222499397893730056830156407331988257383965698358904379729558105489119604343081747549319382873235286788453435066434264212954607441597606413293491628299838317713381567250093086011058119721189087729804152444980
c3 = 8471234074077377509408346140986116360421840978074779990698043926601850838824365885362094731657766299393262223086536737448516669969503891677808275285733096884405583100485903641986516527279324847718603091709062689898441711907846902050004165404073776422495381050861998133576074526490209080137421773440295749900582039873013319584167081936219517593826232230971430937112005615502869367413205660317010303160932970748420125111225082886082306332340892549579826854620461821084886193470846195356695313518639669516456574134135244251956477677377976434266541164893562226872334598362396368708087248848222008201970781942468960022694

# def phase5(n1, c1, n2, c2, n3, c3):
#     r = CRT([c1, c2, c3], [n1, n2, n3])
#     m = int(r) ^ (1 / 13)
#     print(libnum.n2s(int(m))
# phase5(n1, c1, n2, c2, n3, c3)
